JZ56 删除链表中重复的结点

https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef

第一次解

import java.util.*;

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode tmp = pHead;
        LinkedHashMap<Integer, Boolean> map = new LinkedHashMap<>();
        while (tmp != null) {
            ListNode node = tmp;
            
            if (map.containsKey(node.val)) {
                map.put(node.val, false);
            } else {
                map.put(node.val, true);
            }
            
            tmp = tmp.next;
        }
        
        ListNode result = new ListNode(0);
        ListNode node = result;
        tmp = pHead;
        // 重构链表
        while (tmp != null) {
            if (map.get(tmp.val)) {
                node.next = tmp;
                node = node.next;
            }
            tmp = tmp.next;
        }
        // 最后的节点置空
        node.next = null;
        
        return result.next;
    }
}

第二次解

真的很恶心的一题，并不难，但是边界条件要想好

import java.util.*;

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    // 这题关键条件是排序，所以
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) return pHead;
        ListNode result = new ListNode(0);
        ListNode tn = result;
        // 快慢指针
        ListNode pre = pHead;
        ListNode last = pHead.next;
        while (last != null && pre != null) {
            // 如果相同
            if (pre.val == last.val) {
                int temp = last.val;
                // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
                while (last != null && temp == last.val) {
                    last = last.next;
                }
                pre = last;
                if (last != null) last = last.next;
            } else {
                //
                tn.next = new ListNode(pre.val);
                tn = tn.next;
                // 移动指针
                pre = pre.next;
                last = last.next;
            }
        }
        
        if (last == null && pre != null) {
            tn.next = new ListNode(pre.val);
        }
        
        return result.next;
    }
}

第三遍

修改了下指向

public class Solution {
    // 这题关键条件是排序，所以
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) return pHead;
        ListNode result = new ListNode(0);
        result.next = pHead;
        // 快慢指针
        ListNode pre = result;
        ListNode last = result.next;
        while (last!=null) {
            // 如果相同
            if (last.next != null && last.val == last.next.val) {
                // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
                while (last.next!=null && last.val == last.next.val) {
                    last = last.next;
                }
                pre.next = last.next;
                last = last.next;
            } else {
                // 移动指针
                pre = pre.next;
                last = last.next;
            }
        }
        return result.next;
    }
}